/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86187
 * Date: 2022-04-18
 * Time: 23:42
 */

//Scanner scan = new Scanner(System.in);

import java.util.Scanner;

public class Hanoi {

    /**
     * 将 pos1 挪到 pos2 位置
     * @param pos1
     * @param pos2
     */
    public static void move(char pos1, char pos2) {

        System.out.print(pos1+"->"+pos2+" ");
    }

    /**
     * 递归求汉诺塔
     * 核心思想：每一次递归将最下面的盘子放到目的地位置，其余的n-1个盘子放在中间位置
     * @param n     盘子的个数
     * @param pos1  起始位置
     * @param pos2  中间位置
     * @param pos3  目的地位置
     * 注意：随着递归的进行，起始位置、中间位置、目的地位置是会变化的
     */
    public static void hanoi(int n,char pos1,char pos2,char pos3) {
        if(n == 1) {
            int m = 0;
            move(pos1,pos3);
        } else {
            hanoi(n-1,pos1,pos3,pos2);//该步骤是将起始位置的上面n-1个盘子放到中间位置
            move(pos1,pos3);//将最下面的盘子放到目的地位置
            hanoi(n-1,pos2,pos1,pos3);//继续如上所描述的进行递归，直到n==1
        }

    }

    public static void main(String[] args) {

        //1个盘子：A->C     1次：2^1-1
        //2个盘子：A->B A->C B->C      3次:2^2-1
       // 3个盘子：A->C A->B C->B A->C B->A B->C A->C      7次：2^3-1

        hanoi(1,'A','B','C');
        System.out.print("     需移动" +(int)(Math.pow(2,1)-1)+"次");
        System.out.println();
        hanoi(2,'A','B','C');
        System.out.print("     需移动" +(int)(Math.pow(2,2)-1)+"次");
        System.out.println();
        hanoi(3,'A','B','C');
        System.out.print("     需移动" +(int)(Math.pow(2,3)-1)+"次");
        System.out.println();
        hanoi(4,'A','B','C');
        System.out.print("     需移动" +(int)(Math.pow(2,4)-1)+"次");
        System.out.println();

    }
}
